package br.edu.unifei.mestrado.kl;

import java.util.ArrayList;
import java.util.Date;
import java.util.List;

import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

import br.edu.unifei.mestrado.commons.graph.GraphProperties;
import br.edu.unifei.mestrado.commons.graph.GraphWrapper;
import br.edu.unifei.mestrado.commons.graph.NodeWrapper;
import br.edu.unifei.mestrado.commons.graph.RelationshipWrapper;
import br.edu.unifei.mestrado.commons.partition.AbstractPartition;
import br.edu.unifei.mestrado.commons.partition.AbstractPartitionIndex;
import br.edu.unifei.mestrado.commons.partition.BestPartition;
import br.edu.unifei.mestrado.commons.view.ViewListener;
import br.edu.unifei.mestrado.kl.util.DArray;
import br.edu.unifei.mestrado.kl.util.Gain;
import br.edu.unifei.mestrado.kl.util.GainZeroException;
import br.edu.unifei.mestrado.kl.util.PairGain;
import br.edu.unifei.mestrado.kl.util.Partition;

public abstract class KL implements ViewListener {

	private Logger logger = LoggerFactory.getLogger(this.getClass());

	private static int NUMBER_OF_ITERATIONS = 10; //TODO: precisa corrigir para esse nao ser o criterio de parada.

	public void readGraph() {
		getGrafo().readGraph();
	}

	/**
	 * Recupera o objeto grafo especializado.
	 * 
	 * @return
	 */
	protected abstract GraphWrapper getGrafo();

	public abstract AbstractPartitionIndex getPartitionIndex();

	/**
	 * Retorna uma aresta wrapper para a aresta verdadeira entre va e vb. Retornar null se não exisistir a
	 * aresta verdadeira.
	 * 
	 * @param va
	 * @param vb
	 * @return
	 */
	public RelationshipWrapper getArestaLinking(NodeWrapper va, NodeWrapper vb) {
		return getGrafo().getArestaLinking(va, vb);
	}

	/*
	 * Calcula o custo.
	 */
	protected void calculateCost(DArray dValues, final Partition partition) {
		long delta = System.currentTimeMillis();

		// UTIL: calcula o custo baseado nas arestas dos vertices
		// UTIL: para KL, calcula de todos os vertices de cada partição
		// UTIL: para BKL, calcula somente dos vertices da fronteira de cada partição
		//TODO: verificar se dá para tirar esse partition.getAllNodes() daqui
		for (NodeWrapper node : partition.getAllNodes()) {
			if (!node.hasProperty(GraphProperties.ID)) {
				continue;
			}
			calculateDForNode(node, dValues);
		}
		// logger.warn("E: ");
		// Util.mostrarArray(custo.getExtCost(), grafo.getVertexCount());
		// logger.warn("I: ");
		// Util.mostrarArray(custo.getIntCost(), grafo.getVertexCount());
		logger.debug("D: {}", dValues);
		delta = System.currentTimeMillis() - delta;
		logger.warn("Tempo gasto para calcular o custo inicial:" + delta + " ms");
	}

	/**
	 * Calcula o valor de D para o vertice.
	 * 
	 * @param node
	 */
	protected void calculateDForNode(NodeWrapper node, DArray dValues) {
		int intCost = 0;
		int extCost = 0;
		for (RelationshipWrapper aresta : node.getRelationships()) {
			NodeWrapper other = aresta.getOtherNode(node);
			// UTIL: se a partição for igual, então é custo interno, senão é custo externo
			if (node.getPartition() == other.getPartition()) {
				// calcula o peso entre elementos do mesmo grupo
				intCost += aresta.getWeight();
			} else {
				// calcula o peso entre elementos de grupos diferentes
				extCost += aresta.getWeight();
			}
		}
		node.setD(extCost - intCost);
		dValues.addVertex(node, node.getPartition());
	}

	/*
	 * Recalcula o custo.
	 */
	protected void recalculateCost(PairGain pair, DArray dValues) {
		NodeWrapper ai = pair.getI();
		NodeWrapper bi = pair.getJ();

		// UTIL: só recalcula o D para os vertices que tem arestas para ai ou bi
		// Os outros ganhos não precisam ser recalculados
		Iterable<RelationshipWrapper> edges = ai.getRelationships();
		updateD(ai, edges, dValues);
		edges = bi.getRelationships();
		updateD(bi, edges, dValues);
		logger.debug("D recalculados: {}", dValues);
	}

	protected void updateD(NodeWrapper baseNode, Iterable<RelationshipWrapper> edges, DArray dValues) {
		for (RelationshipWrapper aresta : edges) {
			NodeWrapper other = aresta.getOtherNode(baseNode);
			// se o vertice ainda não foi trocado
			if (other.isLocked() == false) {// TODO: verificar pq o other pode não estar no corte,
				// no caso do
				// bkl
				int D = 0;
				if (other.getPartition() == baseNode.getPartition()) {
					// soma o custo, pois a aresta ai/bi vai sair da partição
					D = other.getD() + 2 * aresta.getWeight();
				} else {
					// subtrai o custo, pois a aresta ai/bi vai entrar na partição
					D = other.getD() - 2 * aresta.getWeight();
				}

				// UTIL: precisa remover, alterar o D, e inserir novamente, pra funcionar corretamente
				dValues.updateDValueForVertex(other, other.getPartition(), D);
			}
		}
	}

	/*
	 * Calcula o ganho.
	 */
	protected Gain calculateGain(DArray dValues) {
		Gain ganho = new Gain();

		// UTIL: tem que calcular o ganho, mesmo se os vertices não forem adjacentes
		// então tem que pegar todos por todos dos vertices
		// só as arestas não serve, pq as arestas pegam só vertices adjacentes.

		int count = 0;
		long delta = System.currentTimeMillis();
		for (NodeWrapper va : dValues.getSet1()) {
			for (NodeWrapper vb : dValues.getSet2()) {
				// UTIL: o DArray já está separado por particao e tem só os vertices não usados
				RelationshipWrapper aresta = getArestaLinking(va, vb); // TODO: UTIL: isso está deixando muito
				// lento
				calculateGainForNodes(ganho, va, vb, aresta);

				count++;
			}
		}
		delta = System.currentTimeMillis() - delta;

		logger.debug("Tempo gasto para calcular " + ganho.getSize() + " ganhos: " + delta + " ms | count: "
				+ count);

		return ganho;
	}

	/**
	 * Calcula o ganho relativo a troca de va com vb. A peso da aresta é usada no calculo do ganho. <br>
	 * 
	 * Quando chama esse método, a partição de va é diferente de vb
	 * 
	 * @param ganho
	 * @param va
	 * @param vb
	 * @param aresta
	 */
	protected void calculateGainForNodes(Gain ganho, NodeWrapper va, NodeWrapper vb,
			RelationshipWrapper aresta) {
		int costFromIToJ;
		if (aresta != null) {
			costFromIToJ = aresta.getWeight();
		} else {
			costFromIToJ = 0;
		}
		int gainValue = va.getD() + vb.getD() - 2 * costFromIToJ;
		if (gainValue < 0) {
			if (!acceptNegativeGain()) {// se for BKL, não pode incluir ganho negativo
				return;
			}
		}
		// UTIL: sempre salva o va como sendo o vertice da particao 1 e vb da particao 2
		if (va.getPartition() == Partition.PART_1) {
			ganho.addPair(va, vb, gainValue);
		} else {
			ganho.addPair(vb, va, gainValue);
		}

	}

	/**
	 * Método usado para indicar se é KL ou BKL.
	 * 
	 * O BKL precisa reimplementar esse método retornando false;
	 * 
	 * @return
	 */
	protected boolean acceptNegativeGain() {
		return true;
	}

	/*
	 * Escolhe o melhor par (maior ganho).
	 */
	protected PairGain choosePair(Gain ganhos, DArray dValues) throws GainZeroException {

		ganhos.printGains(20);

		// se não existir o melhor, lança GainZeroException
		PairGain pair = ganhos.getBestGain();
		if (pair.getGain() <= 0) {
			throw new GainZeroException("Encontrou par com ganho ZERO ou NEGATIVO. Terminar a iteracao.");
		}

		logger.debug("Par escolhido: " + pair.toHumanString());

		// marca os elementos para não serem usados em futuros processamentos
		pair.getI().lock();
		pair.getJ().lock();

		int pI = pair.getI().getPartition();
		int pJ = pair.getJ().getPartition();

		dValues.removeVertex(pair.getI(), pI);
		dValues.removeVertex(pair.getJ(), pJ);
		return pair;
	}

	/*
	 * Executa a troca, se existir.
	 */
	protected int performExchange(List<PairGain> list, int it, Partition partition) {
		int k = 0;
		int k_tmp = 0;

		int G = 0;
		int G_tmp = 0;

		for (PairGain pair : list) {
			G_tmp += pair.getActualGain();
			k_tmp++;

			// NÂO È ISSO: se o ganho até aqui for maior que zero
			// UTIL: E SIM ISSO: se o ganho total for maior ou igual que algum ganho total anterior
			// UTIL: é maior ou igual(SO MAIOR), para evitar o minimo local ( O MINIMO LOCAL JA FOI
			// UTIL: CONSIDERADO, PQ PODE TER NEGATIVO NO INCLUSO NO TOTAL
			if (G_tmp >= G && G_tmp > 0) {
				// armazena somente até as trocas para o melhor ganho
				k = k_tmp;
				G = G_tmp;
			}
		}
		int cutWeight = -1;
		if (k > 0) {
			partition.exchangePairs(list, k);
			partition.printPartitions();
			cutWeight = partition.getCutWeight();
		}

		if (cutWeight == -1) {
			logger.warn("End of IT " + it + ". " + " Qtd de trocas: " + k + " ganho total: " + G
					+ " No exchanges made.");
		} else {
			logger.warn("End of IT " + it + ". " + " Qtd de trocas: " + k + " ganho total: " + G
					+ " cutWeight: " + cutWeight);
		}

		return cutWeight;
	}

	/**
	 * Iteração KL.
	 * 
	 * @param it
	 *            Número da iteração.
	 * @param partition
	 *            Partição usada para fazer as trocas necessarias
	 * @return O valor do corte.
	 */
	protected int klIteration(int it, Partition partition) {
		long delta = System.currentTimeMillis();
		long tGanhoI = 0, tGanho = 0, tChoose = 0, tRecalc = 0;
		long dl = 0;
		int count = 0;

		List<PairGain> list = new ArrayList<PairGain>();
		DArray dValues = new DArray();

		logger.warn("Iteracao KL " + it);
		logger.debug("Initial partitions:");
		partition.printPartitions();
		// 1 - calcula o custo
		calculateCost(dValues, partition);
		// 2 - calcular o ganho
		dl = System.currentTimeMillis();
		Gain ganhos = calculateGain(dValues);
		dl = System.currentTimeMillis() - dl;
		tGanhoI += dl;

		repaint();
		
		while (ganhos.getSize() > 0) {
			count++;
			PairGain choosen = null;
			try {
				dl = System.currentTimeMillis();
				choosen = choosePair(ganhos, dValues);
				dl = System.currentTimeMillis() - dl;
				
				repaint();
				tChoose += dl;
			} catch (GainZeroException e) {
				logger.debug("Nenhum ganho disponível mais.");
				break;
			}

			// UTIL: cria um novo par, para desacoplar os nos escolhidos dos originais, que serao modificados
			// no decorrer do processamento.
			PairGain newPair = new PairGain(choosen);
			// 3 - armazenar o maior ganho, melhor par
			list.add(newPair);
			// 4 - Atualizar os valores de D
			dl = System.currentTimeMillis();
			recalculateCost(choosen, dValues);
			dl = System.currentTimeMillis() - dl;
			tRecalc += dl;

			// 2 - calcular o ganho
			dl = System.currentTimeMillis();
			ganhos = calculateGain(dValues);
			dl = System.currentTimeMillis() - dl;
			tGanho += dl;

			repaint();
		}

		//TODO: precisa fazer outro loop e colocar G <= como criterio de parada
		
		int cutWeight = performExchange(list, it, partition);
		delta = System.currentTimeMillis() - delta;

		repaint();
		
		logger.debug("Tempos: tGanhoI: " + tGanhoI + " tGanho: " + tGanho + " tChoose: " + tChoose
				+ " tRecalc: " + tRecalc + " count: " + count);
		logger.warn("Tempo gasto na iteração " + it + ": " + delta + " ms");

		return cutWeight;
	}

	/*
	 * Metodo KL.
	 */
	public BestPartition executeKL() {
		if (getGrafo().getSizeNodes() > 200) {
			setShowView(false);
			logger.warn("Desabilitando exibição dos do grafo. qtd de vertices > 200");
		}
		initView(getGrafo());
		
		Partition partition = new Partition(AbstractPartition.NO_LEVEL, getPartitionIndex());
		try {
			long delta = System.currentTimeMillis();
			getGrafo().beginTransaction();
			partition.initialFixedPartition(getGrafo().getAllNodes());
			getGrafo().endTransaction();
			delta = System.currentTimeMillis() - delta;
			repaint();
			logger.warn("Tempo gasto na initialFixedPartition : " + delta + " ms");
		} finally {
			getGrafo().finish();
		}

		int bestCut = partition.getCutWeight();
		logger.debug("Corte inicial: " + bestCut);

		BestPartition bestPartition = partition.createBestPartition();

		int it = 0;
		int cut = 0;
		int bestIt = 0;
		for (it = 0; it < NUMBER_OF_ITERATIONS; ++it) {
			try {
				getGrafo().beginTransaction();

				getGrafo().unlockAllNodes();
				
				repaint();

				cut = klIteration(it, partition);

				// se não houve trocas
				if (cut == -1) {
					// tenta outra partição arbitrária.
					partition.initialArbitraryPartition(it, getGrafo().getAllNodes());
				} else {
					// usa a mesma partição atual, como sendo a partição inicial do passo seguinte
					if (cut < bestCut) {
						// armazena o melhor resultado
						bestIt = it;
						bestPartition = partition.createBestPartition();
						bestCut = cut;
					}
				}
				logger.debug("Melhor corte: " + bestCut + " Iteração " + bestIt);
				getGrafo().endTransaction();
			} finally {
				getGrafo().finish();
			}
		}
		return bestPartition;
	}

	public void execute() {
		try {
			getGrafo().beginTransaction();
			readGraph();
			getGrafo().endTransaction();
		} finally {
			getGrafo().finish();
		}

		try {
			long time = System.currentTimeMillis();
			BestPartition result = executeKL();

			time = System.currentTimeMillis() - time;
			logger.warn("Fim do KL. Tempo gasto: " + time + " ms File: " + getGrafo().getGraphFileName()
					+ " - Hora Termino: " + new Date());
			result.printSets();
		} catch (Throwable e) {
			logger.error("Erro executando KL.", e);
		} finally {
			getGrafo().finish();
		}
	}
}
